from BuildTree import *


class Solution:
    def maxSumBST(self, root: Optional[TreeNode]) -> int:
        self.ans = 0

        class Info:
            def __init__(self, isBST=True, minv=inf, maxv=-inf, summ=0):
                self.isBST = isBST
                self.min = minv
                self.max = maxv
                self.sum = summ

        def dfs(node: Optional[TreeNode]) -> Info:
            if not node:
                return Info()

            l = dfs(node.left)
            r = dfs(node.right)

            # 初始化当前结果
            if l.isBST and r.isBST and (l.max < node.val < r.min):
                summ = l.sum + r.sum + node.val
                self.ans = max(self.ans, summ)  # 更新全局最大和
                return Info(True, min(l.min, node.val), max(r.max, node.val), summ)
            else:
                return Info(False)

        dfs(root)
        return self.ans


if __name__ == '__main__':
    s = Solution()
    root = build_tree_from_level_order([4, 8, null, 6, 1, 9, null, -5, 4, null, null, null, -3, null, 10])
    r = s.maxSumBST(root)
    print(r)
